home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_1 / prime.tes < prev    next >
Text File  |  1995-03-23  |  7KB  |  232 lines
  1. Article 2790 of comp.sys.handhelds:
  2. Path: en.ecn.purdue.edu!noose.ecn.purdue.edu!samsung!sol.ctr.columbia.edu!ira.uka.de!fauern!fauern!faui1f!kskalb
  3. From: kskalb@faui1f.informatik.uni-erlangen.de (Klaus Kalb)
  4. Newsgroups: comp.sys.handhelds
  5. Subject: HP48: primality testing
  6. Keywords: primality
  7. Message-ID: <kskalb.660525843@faui1f>
  8. Date: 6 Dec 90 23:24:03 GMT
  9. Sender: root@medusa.informatik.uni-erlangen.de
  10. Lines: 218
  11.  
  12.  
  13. Hello everybody,
  14.  
  15. This program for the HP48 tests numbers for being prime.
  16. It is written as a user defined function, so you can include
  17. it into algebraics.
  18.  
  19. Start it with a number (binary or real) in level 1 and it will answer:
  20.  0 if the number is composite
  21.  1 if the number is prime
  22.  2 if it can't do the job 
  23.  
  24. The last case occurs only if the number is greater then 25*10^9.
  25. Even if this occurs, you can be quite sure that the given number
  26. is a prime, since the numbers that give a 2 on this test and are
  27. composite are very rare --- but they do exist.
  28. (they are indeed so rare that I don't know an example ;-)
  29.  
  30. This test is fast --- testing a prime near 10^9 will take about 7000 ticks.
  31. This is less then one second --- not so bad for a small machine.
  32.  
  33. Of course this is accomplished using mcode. You need ASC\-> to get it
  34. into your machine.
  35.  
  36. ------------------------------------------------------------------------------
  37.  
  38. MORE ABOUT THE IMPLEMENTATION:
  39.  
  40.   This program implements the test proposed by Pomerance, Selfridge and
  41.   Wagstaff in _The_Pseudoprimes_to_25*10^9_ in math.comp.35 (1980)
  42.  
  43.   Some special effort is made to recognize small primes and numbers with
  44.   small factors on an early stage.
  45.  
  46.   It will recognize all primes below 25*10^9.
  47.  
  48.   It runs the strong pseudoprime test with the bases 2,3,5,7, so that
  49.   a number passing this test with result 2 is at least a strong pseudoprime
  50.   to these bases.
  51.  
  52.   There are two subroutines written in mcode:
  53.  
  54.     BGCD     calculates the greatest common divisor of two binary integers.
  55.              It uses the binary algorithm that can be found in Knuth's
  56.               _The_Art_of_Computer_Programming.
  57.  
  58.     MILRAB   performs a strong pseudoprime test on the number N in level 2
  59.              to the base B in level 1. It will accept any combination of
  60.              binary integers and reals. The output is 1 if N is a
  61.              strong base-B pseudoprime and 0 if not.
  62.  
  63.   Both routines perform argument checking and give decent error messages.
  64.  
  65. ------------------------------------------------------------------------------
  66.  
  67. INSTALLATION:
  68.    
  69.   Download the following object to your HP48 using the name 'PRIME'.
  70.   Be sure that ASC\-> can be found in the path.
  71.   Evaluate 'PRIME'. Answer 'YES' be pressing the 'A' key.
  72.  
  73.   After this, you may purge 'PRIME'.
  74.  
  75.   Three Programs will be installed on the current directory:
  76.     BGCD, MILRAB and PRIME?
  77.  
  78. ------------------------------------------------------------------------------
  79.  
  80. DISCLAIMER: (that's one I've found on the net ;-)
  81.  
  82.      This program makes use of undocumented low-level features of
  83.      the HP48SX calculator, and may or may not cause loss of data,
  84.      excessive battery drainage, and/or damage to the calculator
  85.      hardware.  The Author takes no responsibility whatsoever for 
  86.      any damage caused by the use of this program.
  87.  
  88.      This software is provided "as is" and WITHOUT ANY EXPRESS OR
  89.      IMPLIED WARRANTIES, including, but not limited to, THE IMPLIED
  90.      WARRANTIES OF MERCHANTABILITY and FITNESS FOR A PARTICULAR PURPOSE.
  91.  
  92. ------------------------------------------------------------------------------
  93.    Klaus Kalb    | mail :  IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany   
  94.                  | email:  kskalb@immd1.informatik.uni-erlangen.de   
  95. ------------------------------------------------------------------------------
  96.  
  97. %%HP: T(3)A(D)F(,);
  98. @
  99. @ PRIME (generated by hp48pack at 07.12.90)
  100. @
  101. @$NAME     PRIME
  102. @$DATE     06.12.90
  103. @$VERSION  2.00
  104. @
  105. @
  106. @ PRIME?         2.00 06.12.90
  107. @ BGCD           1.00 
  108. @ MILRAB         1.00 
  109. @
  110. @
  111. \<< CLLCD
  112.   "----------------------" DUP 1 DISP
  113.   "PRIME    2.00 06.12.90" 2 DISP
  114.    DUP 3 DISP
  115.    "    PRIMALITY TEST" 4 DISP
  116.    "    by Klaus Kalb" 5 DISP
  117.    6 DISP
  118.   " unpack ?" 7 DISP
  119.   0
  120. @
  121. @ $NAME    PRIME?
  122. @ $DATE    06.12.90
  123. @ $VERSION 2.00
  124. @
  125.  
  126. \<<
  127.     \-> n 
  128.     \<<
  129.       RCLF 64 STWS        @ save the flag status 
  130.  
  131.       @ check the argument
  132.       n DTAG
  133.       IF DUP TYPE NOT
  134.       THEN
  135.         ABS DUP R\->B DUP B\->R ROT
  136.     IF SAME THEN 
  137.           0
  138.         ELSE
  139.           515            @ bad argument value
  140.         END
  141.       ELSE
  142.         IF DUP TYPE 10 SAME THEN
  143.           0
  144.         ELSE
  145.           514            @ bad argument type
  146.         END
  147.       END
  148.       
  149.       @ make an error
  150.       IF DUP THEN 
  151.         ROT STOF
  152.     SWAP DROP
  153.         IF -55 FC? THEN n SWAP END
  154.     DOERR
  155.       END
  156.  
  157.       DROP
  158.       'n' STO
  159.  
  160.       CASE
  161.         n #2d <                 THEN 0 END
  162.         { #2d #3d #5d #7d } n POS        THEN 1 END
  163.         #210d n BGCD #1d \=/            THEN 0 END
  164.         #121d n >                THEN 1 END
  165.         #9156001667401012567d  n BGCD #1d \=/    THEN 0 END
  166.         #12474161705592459703d n BGCD #1d \=/    THEN 0 END
  167.     #11449d n >                THEN 1 END
  168.     n 2 MILRAB NOT                THEN 0 END
  169.     #42799d n >                THEN 1 END
  170.     n 3 MILRAB NOT                THEN 0 END
  171.     #1373653d n >                THEN 1 END
  172.     n 5 MILRAB NOT                THEN 0 END
  173.     #25326001d n >                THEN 1 END
  174.     n 7 MILRAB NOT                THEN 0 END
  175.     #3215031751d n ==            THEN 0 END
  176.     #25000000000d n >            THEN 1 END
  177.         2
  178.       END
  179.       
  180.       SWAP STOF
  181.       
  182.     \>>
  183. \>>
  184. @ $END PRIME?
  185.  
  186. 'PRIME?'
  187.  
  188. @ $NAME    BGCD
  189. @ $VERSION 1.00
  190. @
  191. "D9D20E1632FDE81ECD46CCD20F70008F77F35AF397845AFE978C48087091AFE8
  192. 0870F081E81CB7765EF808B09081E65FF9F650AFEB7A9780181C808608F65EFA
  193. FA97BC0A74A7F64FF8F59E3593632B21302438"
  194.  
  195. ASC\->
  196. @ $END BGCD
  197.  
  198. 'BGCD'
  199.  
  200. @ $NAME    MILRAB
  201. @ $VERSION 1.00
  202. @
  203. "D9D20E1632FDE8199040D9D209F345322309F34532230CCD20900006380B2130
  204. 4CD46D9D209F345CCD20900006160B2130DF040D9D20322309F34532230CCD20
  205. 900006530B2130ECD46D9D202C230CA13050F353DE350BE35CCD20431008F77F
  206. 3510A1008087093978D0A7CA7C9789120808244B2A28F07F35808C20808249C2
  207. A268EFA7C9783DAF381CB77808605F101AF0B74103111978E380870F181C1011
  208. 1211A7950102111808605E11311A7240103111A7C97CDC113AF2B7697202118A
  209. 7E97251A7F97B11AF67C0065EF6B5F604FAF19780080870D181CA761209F650B
  210. 72120808607EA71A7C1209F050B7812097CECAF401B213093632B213010A4"
  211.  
  212. ASC\->
  213. @ $END MILRAB
  214.  
  215. 'MILRAB'
  216.  
  217. @ user dialog
  218.  
  219.   { { "YES" \<< WHILE DUP 0 SAME NOT
  220.              REPEAT STO END DROP
  221.              " PRIME installed." 7 DISP 3 FREEZE
  222.              0 MENU \>> }
  223.              "" "" "" "" 
  224.     { "NO" \<< WHILE DUP 0 SAME NOT
  225.              REPEAT DROP DROP END DROP
  226.              0 MENU \>> }
  227.   } 3 FREEZE TMENU \>> 
  228.  
  229. @$END PRIME
  230.  
  231.  
  232.